package com.base.leetcode;

import com.base.dataStructure.queue.LinkedListQueue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: hdhao
 * @Create: 2023/4/2 - 17:33
 * @Version: v1.0
 */
//二叉树的Z字层序遍历
public class Leetcode103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root){
        List<List<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        //创建一个队列
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        //将根节点插入队列尾部
        queue.offer(root);
        //循环遍历队列(当队列不为空的时候,说明还未遍历完成)
        int c1 = 1;//当前层的节点数
        boolean odd = true;//奇数层
        while (!queue.isEmpty()){
            LinkedList<Integer> level = new LinkedList<>();
            int c2 = 0;//下一层节点数
            for (int i = 0; i < c1; i++){
                //从队列头部获取节点并删除队列中的节点
                TreeNode n = queue.poll();
                if (odd) {
                    level.offerLast(n.val);
                }else {
                    level.offerFirst(n.val);
                }

                //判断该节点是否还有左节点
                if (n.left!= null){
                    //如果还有左节点,将左节点加入队列中
                    queue.offer(n.left);
                    c2++;
                }
                //判断该节点是否还有右节点
                if (n.right!= null){
                    //如果还有右节点,将右节点加入队列中
                    queue.offer(n.right);
                    c2++;
                }
            }
            odd = !odd;
            result.add(level);
            c1 = c2;
        }
        return result;
    }

}
